package uestc.lj.basic.recall;

/**
 * 回溯算法：
 * n皇后问题
 *
 * @Author:Crazlee
 * @Date:2021/11/24
 */
public class Code01_NQueens {
	/**
	 * n皇后求解问题
	 *
	 * @param n n*n的棋盘
	 * @return
	 */
	public static int num1(int n) {
		if (n < 1) {
			return 0;
		}
		//record[i]代表第i行的皇后放在了第几列
		int[] record = new int[n];
		return process1(0, record, n);
	}

	/**
	 * 求解过程
	 *
	 * @param i      第几行
	 * @param record 记录皇后放在哪一列的数组
	 * @param n      棋盘
	 * @return 合法的皇后放置位置的数量
	 */
	public static int process1(int i, int[] record, int n) {
		//来到了终止行
		if (i == n) {
			return 1;
		}
		int res = 0;
		//当前行是i行，尝试i行的所有列j
		for (int j = 0; j < n; j++) {
			if (isValid(record, i, j)) {
				record[i] = j;
				//对于当前i和j来说满足条件，继续递归到下一行的所有列
				res += process1(i + 1, record, n);
			}
		}
		return res;
	}

	/**
	 * 检查皇后放置合法性
	 *
	 * @param record 记录之前皇后放置的位置
	 * @param i      第i行
	 * @param j      第j列
	 * @return 是否合法
	 */
	public static boolean isValid(int[] record, int i, int j) {
		//从之前的i行开始寻找是否共列或共线
		for (int k = 0; k < i; k++) {
			if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
				return false;
			}
		}
		return true;
	}

//======================位运算优化========================================================================================

	public static int num2(int n) {
		if (n < 1 || n > 32) {
			return 0;
		}
		int upperLim = n == 32 ? -1 : (1 << n) - 1;
		return process2(upperLim, 0, 0, 0);
	}

	/**
	 * 使用位运算来优化n皇后问题
	 *
	 * @param upperLim    n位1的二进制数
	 * @param colLim      之前的皇后对现在的列的限制，1不能放，0可以放
	 * @param leftDiaLim  之前的皇后对现在的左斜线的限制
	 * @param rightDiaLim 之前的皇后对现在的右斜线的限制
	 * @return 可以放n皇后的种类
	 */
	public static int process2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim) {
		// 终止条件
		if (colLim == upperLim) {
			return 1;
		}

		int pos = 0;
		int mostRightOne = 0;

		//所有候选皇后的位置
		pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));

		int res = 0;
		while (pos != 0) {
			//取最右侧1
			mostRightOne = pos & (~pos + 1);
			//尝试将皇后放在最右侧1的位置
			pos = pos - mostRightOne;
			//更新
			res += process2(upperLim, colLim | mostRightOne,
					(leftDiaLim | mostRightOne) << 1,
					(rightDiaLim | mostRightOne) >>> 1);
		}
		return res;
	}

	public static void main(String[] args) {
		int n = 14;

		long start = System.currentTimeMillis();
		System.out.println(num2(n));
		long end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + "ms");

		start = System.currentTimeMillis();
		System.out.println(num1(n));
		end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + "ms");

	}
}
